package array

// 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）
// 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列
// target==9 输出 [[2,3,4],[4,5]]

// 滑动窗口解法 时间复杂度on

func FindContinuousSequence(target int) [][]int {
	// i 滑动窗口的左边界
	// j 滑动窗口的右边界
	// sum 滑动窗口中数字的和
	i, j, sum := 1, 1, 0
	ret := make([][]int, 0)
	for i <= target/2 {
		if sum < target {
			sum += j
			j++ // 右边界向右移动
		} else if sum > target {
			sum -= i
			i++ // 左边界向右移动
		} else {
			// 记录结果
			tmp := make([]int, 0, j-1) // 一个tmp代表一组解
			for k := i; k < j; k++ {   // [i,j) 左闭右开
				tmp = append(tmp, k)
			}
			ret = append(ret, tmp) // ret代表所有可能的解
			sum -= i
			i++ // 左边界向右移动
		}
	}
	return ret
}
